package com.sjf.day02.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author <huangtang>
 * @since 2021/12/27 13:18
 **/
public class InsertSort {

    public static void main(String[] args) {
        int[] num = {101,34,119,1,-89,72};
        //int[] num = new int[100000];
        //for (int i = 0; i < 100000; i++) {
        //    num[i] = (int)(Math.random() * 1000000); //生产 0 - 100000的随机数
        //}
        //long t1 = System.currentTimeMillis();
        insertSort2(num);
        //System.out.println("用时："+(System.currentTimeMillis()-t1)); //1072ms
    }

    /**
     * 插入排序
     * @param num 需要排序的数组
     */
    public static void insertSort(int[] num){
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < num.length; i++) {
            //拿到待插入的数
            insertVal=num[i];
            //获取要插入数的前面一个数
            insertIndex = i -1;
            //当下标大于等于0 并且插入值小于前一个数
            while(insertIndex >=0 && insertVal < num[insertIndex]){
                num[insertIndex+1] = num[insertIndex]; //先将大于的数向后移
                insertIndex--; //再将下标前移继续遍历
            }
            if(insertIndex+1!=i){
                //找到要插入的位置，赋值即可
                num[insertIndex+1] = insertVal;
            }
            System.out.printf("第 %d 轮插入%s \n",i,Arrays.toString(num));
        }
    }

    public static void insertSort2(int[] num){
        int insertVal = 0;//要插入的值
        int insertIndex = 0;//要插入的索引
        for (int i = 1; i < num.length; i++) {
            insertVal = num[i];//要插入的值为未排序数组的后一个数
            insertIndex = i-1; //插入位置为要插入数的前一个位置
            //当下标大于等于0 并且插入值小于前一个数
            while (insertIndex >= 0 && insertVal < num[insertIndex]){
                //先将大于的数向后移
                num[insertIndex+1] = num[insertIndex];
                //再将下标前移继续遍历
                insertIndex--;
            }
            //找到要插入的位置，赋值即可
            if(insertIndex+1!=i){ //!=i意为不在原位置上
                //insertIndex位置上的值是小于插入值的，所以需要在该位置上后一位赋值
                num[insertIndex+1] = insertVal;
            }
            System.out.printf("第 %d 轮插入%s \n",i,Arrays.toString(num));
        }
    }
}
